package mess;

public class LeeCode_81 {
    public static void main(String[] args) {
        System.out.println(search(new int[]{1, 3}, 1));
    }

    private static boolean search(int[] nums, int target) {
        int len = nums.length;
        int rightMax = nums[len - 1];
        int k = -1;
        for(int i = 0; i < len - 1; i++){
            if(nums[i] > nums[i + 1]){
                k = i;
                break;
            }
        }
        int start = 0;
        int end = 0;
        if(target > rightMax){
            //左半段
            start = 0;
            end = k;
            while(start < end){
                int mid = (start + end) / 2;
                if(nums[mid] < target){
                    //右边
                    start = mid + 1;
                }else if (nums[mid] == target) {
                    return true;
                } else{
                    //左边
                    end = mid - 1;
                }
            }
        }else{
            //右半段
            start = k == -1 ? 0 : k + 1;
            end = len - 1;
            while(start < end){
                int mid = (start + end) / 2;
                if(nums[mid] < target){
                    //右边
                    start = mid + 1;
                }else if (nums[mid] == target) {
                    return true;
                } else{
                    //左边
                    end = mid - 1;
                }
            }
        }
        return (start < len && target == nums[start]) || (end >= 0 && target == nums[end]);
    }
}
